package sword_offer;

import java.math.BigInteger;

/**
 * @ClassName _14_1_CuttingRope
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/8 20:42
 */
public class _14_2_CuttingRope {

    public static void main(String[] args) {
        _14_2_CuttingRope cuttingRope = new _14_2_CuttingRope();
        int i = cuttingRope.cuttingRope(1000);
        System.out.println(i);
    }

    public int cuttingRope(int n) {
        if (n == 2)
            return 1;
        else if (n == 3)
            return 2;
        int p = 1000000007;
        long result = 1;
        while (n > 4){
            result *= 3;
            result %=p;
            n -= 3;
        }

        return (int) (n * result % p);
    }

}
